//
//  StringSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/1/31.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include "StringSolution.hpp"

using namespace std;

int StringSolution::strStr(string haystack, string needle)
{
    if(needle[0] == '\0')
        return 0;
    int hsize = haystack.size();
    int nsize = needle.length();
    
    // <= is the key.
    for(int i=0;i <= hsize-nsize;i++)
    {
        int j = 0;
        for(;j<nsize;j++)
        {
            if(haystack[i + j] != needle[j])
            {
                break;
            }
        }
        
        if(j == nsize)
            return i;
    }
    return -1;
}

bool StringSolution::isAnagram(string s, string t)
{
//    // Normal
//    if(s.length() != t.length())
//        return false;
//    sort(s.begin(), s.end());
//    srot(t.begin(), t.end());
//    return s == t;
    
    vector<int> table(26, 0);
    for(auto & ch : s)
        table[ch - 'a'] ++;
    
    for(auto & ch : t)
    {
        table[ch - 'a'] --;
        if(table[ch - 'a'] < 0)
            return false;
    }
    return false;
}

vector<vector<string>> StringSolution::groupAnagrams(vector<string>& strs)
{
    // vector<string> index
    unordered_map<string, int> hashmap;
    vector<vector<string>> result;

    int size = strs.size();
    int index = 0;
    for(int i=0;i<size;i++)
    {
        string cur = strs[i];
        sort(cur.begin(), cur.end());
        if(hashmap.find(cur) != hashmap.end())
        {
            result[hashmap[cur]].push_back(strs[i]);
        }
        else
        {
            hashmap[cur] = index ++;
            result.push_back(vector<string>{strs[i]});
        }
    }
    return result;
}

// 注意越界+跳过非字母和数字
// isalnum函数的使用
// 检查费字母和数字检查是否越界
// 不区分大小写
bool StringSolution::isPalindrome(string s)
{
    int size = s.size();
    int left = 0;
    int right = size - 1;
    
    while(left < right)
    {
        while(left < right && !isalnum(s[left]))
              left ++;
        while(left < right && !isalnum(s[right]))
              right --;
        if(left < right)
        {
            if(tolower(s[left++]) != tolower(s[right--]))
                return false;
        }
    }
    return true;
}

// 680. 验证回文字符串 Ⅱ
bool StringSolution::validPalindrome(string s)
{
    int size = s.size();

    int left = 0;
    int right = size - 1;

    int flag = 0;
    int startleft = 0;
    int startright = 0;
    
    while(left < right)
    {
        if(tolower(s[left] == tolower(s[right])))
        {
            left ++;
            right --;
        }
        else
        {
            if(flag == 0)
            {
                startleft = left;
                startright = right;
                right --;
                flag = 1;
            }
            else if(flag == 1)
            {
                left = startleft;
                right = startright;
                left ++;
                flag = 2;
            }
            else
            {
                return false;
            }
        }
    }
    return true;
}

// 266. 回文排列
// 给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。
bool StringSolution::canPermutePalindrome(string s)
{
    unordered_map<int, int> table;
    int size = s.size();
    for(auto& ch : s)
    {
        table[ch] ++;
    }

    int a = 0;
    int b = 0;
    for(auto & value : table)
    {
        if(value.second > 0)
        {
            if(value.second % 2 == 0)
                a ++;
            else
                b ++;
        }
    }

    if(size % 2 == 0 && b > 0)
        return false;
    else if(size % 2 != 0 && b != 1)
        return false;
    return true;
}

// 409. 最长回文串[构造最长的回文的字符个数，直接计算奇数即可，不用枚举]
int StringSolution::longestPalindrome(string s)
{
    int size = s.size();
    unordered_map<int, int> table;
    for(auto & ch : s)
    {
        table[ch] ++;
    }
    int oddcount = 0;
    for(auto & value : table)
    {
        if(value.second % 2 != 0)
            oddcount ++;
    }
    return oddcount == 0 ? size : size - oddcount + 1;
}

vector<int> StringSolution::findAnagrams(string s, string p)
{
    int n = p.length();
    int m = s.length();

    vector<int> result;
    if(n > m)
        return result;

    vector<int> cnt1(26);
    vector<int> cnt2(26);
    for(int i=0;i<n;i++)
    {
        cnt1[p[i] - 'a'] ++;
        cnt2[s[i] - 'a'] ++;
    }
    
    if(cnt1 == cnt2)
        result.push_back(0);
    
    for(int i=n;i<m;i++)
    {
        cnt2[s[i] - 'a'] ++;
        cnt2[s[i - n] - 'a']--;
        if(cnt2 == cnt1)
            result.push_back(i - n + 1);
    }
    return result;
}

// 567. 字符串的排列 和438类似的解题思路
bool StringSolution::checkInclusion(string s1, string s2)
{
    int n = s1.length();
    int m = s2.length();

    vector<int> result;
    if(n > m)
        return false;

    vector<int> cnt1(26);
    vector<int> cnt2(26);
    for(int i=0;i<n;i++)
    {
        cnt1[s1[i] - 'a'] ++;
        cnt2[s2[i] - 'a'] ++;
    }
    
    if(cnt1 == cnt2)
        return false;
    
    for(int i=n;i<m;i++)
    {
        cnt2[s2[i] - 'a'] ++;
        cnt2[s2[i - n] - 'a']--;
        if(cnt2 == cnt1)
            return true;
    }
    return false;
}

// 316. 去除重复字母
// 1081. 不同字符的最小子序列
// 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
// 保持字典顺序
// string smallestSubsequence(string s)
string StringSolution::removeDuplicateLetters(string s)
{
    int size = s.size();
    vector<int> tablevisit(128);
    vector<int> tablecount(128);
    stack<int> stk;
    string result;
    
    for(auto & ch : s)
    {
        tablecount[ch] ++;
    }
    
    for(int i=0;i<size;i++)
    {
        char ch = s[i];
        if(tablevisit[ch] == 0)
        {
            while(!stk.empty() && stk.top() > ch && tablecount[stk.top()] > 0)
            {
                tablevisit[stk.top()] = 0;
                stk.pop();
            }
            stk.push(ch);
        }
        
        tablevisit[ch] = 1;
        tablecount[ch] --;
    }
    
    while(!stk.empty())
    {
        result += stk.top();
        stk.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}
